package com.sheng.leetcode.year2023.month11.day17;

import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2023/11/17
 * <p>
 * 2736. 最大和查询<p>
 * <p>
 * 给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 ，<p>
 * 另给你一个下标从 1 开始的二维数组 queries ，其中 queries[i] = [xi, yi] 。<p>
 * 对于第 i 个查询，在所有满足 nums1[j] >= xi 且 nums2[j] >= yi 的下标 j (0 <= j < n) 中，<p>
 * 找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。<p>
 * 返回数组 answer ，其中 answer[i] 是第 i 个查询的答案。<p>
 * <p>
 * 示例 1：<p>
 * 输入：nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]<p>
 * 输出：[6,10,7]<p>
 * 解释：<p>
 * 对于第 1 个查询：xi = 4 且 yi = 1 ，可以选择下标 j = 0 ，此时 nums1[j] >= 4 且 nums2[j] >= 1 。nums1[j] + nums2[j] 等于 6 ，可以证明 6 是可以获得的最大值。<p>
 * 对于第 2 个查询：xi = 1 且 yi = 3 ，可以选择下标 j = 2 ，此时 nums1[j] >= 1 且 nums2[j] >= 3 。nums1[j] + nums2[j] 等于 10 ，可以证明 10 是可以获得的最大值。<p>
 * 对于第 3 个查询：xi = 2 且 yi = 5 ，可以选择下标 j = 3 ，此时 nums1[j] >= 2 且 nums2[j] >= 5 。nums1[j] + nums2[j] 等于 7 ，可以证明 7 是可以获得的最大值。<p>
 * 因此，我们返回 [6,10,7] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]<p>
 * 输出：[9,9,9]<p>
 * 解释：对于这个示例，我们可以选择下标 j = 2 ，该下标可以满足每个查询的限制。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]<p>
 * 输出：[-1]<p>
 * 解释：示例中的查询 xi = 3 且 yi = 3 。对于每个下标 j ，都只满足 nums1[j] < xi 或者 nums2[j] < yi 。因此，不存在答案。<p>
 * <p>
 * 提示：<p>
 * nums1.length == nums2.length<p>
 * n == nums1.length<p>
 * 1 <= n <= 10^5<p>
 * 1 <= nums1[i], nums2[i] <= 10^9<p>
 * 1 <= queries.length <= 10^5<p>
 * queries[i].length == 2<p>
 * xi == queries[i][1]<p>
 * yi == queries[i][2]<p>
 * 1 <= xi, yi <= 10^9<p>
 */
public class LeetCode2736 {

    @Test
    public void test01() {
        int[] nums1 = {4, 3, 1, 2}, nums2 = {2, 4, 9, 5};
        int[][] queries = {{4, 1}, {1, 3}, {2, 5}};
//        int[] nums1 = {3, 2, 5}, nums2 = {2, 3, 4};
//        int[][] queries = {{4, 4}, {3, 2}, {1, 1}};
//        int[] nums1 = {2, 1}, nums2 = {2, 3};
//        int[][] queries = {{3, 3}};
        System.out.println(Arrays.toString(new Solution().maximumSumQueries(nums1, nums2, queries)));
    }
}

class Solution {
    int sz;
    int[] tr;

    int lowbit(int x) {
        return x & -x;
    }

    void add(int a, int b) {
        for (int i = a; i <= sz; i += lowbit(i)) {
            tr[i] = Math.max(tr[i], b);
        }
    }

    int query(int x) {
        int ans = -1;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans = Math.max(ans, tr[i]);
        }
        return ans;
    }

    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length, m = queries.length;
        // 构建新的 nums 和 nq
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i] = new int[]{nums1[i], nums2[i]};
        }
        int[][] nq = new int[m][3];
        for (int i = 0; i < m; i++) {
            nq[i] = new int[]{queries[i][0], queries[i][1], i};
        }

        // 对要添加到树状数组的 nums[i][1] 和 nq[i][1] 进行离散化（构建映射字典, 将原值映射到 [0, m - 1])
        Set<Integer> set = new HashSet<>();
        for (int[] x : nums) {
            set.add(x[1]);
        }
        for (int[] q : nq) {
            set.add(q[1]);
        }
        List<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        sz = list.size();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < sz; i++) {
            map.put(list.get(i), i);
        }

        // 调整询问顺序, 解决其中一维限制
        Arrays.sort(nums, (a, b) -> b[0] - a[0]);
        Arrays.sort(nq, (a, b) -> b[0] - a[0]);

        tr = new int[sz + 10];
        Arrays.fill(tr, -1);

        int[] ans = new int[m];
        int idx = 0;
        for (int[] q : nq) {
            int x = q[0], y = q[1], i = q[2];
            // 扫描所有满足 nums[idx][0] >= x 的数对, 添加到树状数组中（其中离散值作为位置信息, 数对和作为值信息）
            while (idx < n && nums[idx][0] >= x) {
                add(sz - map.get(nums[idx][1]), nums[idx][0] + nums[idx][1]);
                idx++;
            }
            // 查询树状数组中的最值
            ans[i] = query(sz - map.get(y));
        }
        return ans;
    }
}
